﻿#pragma once
#include <vector>
#include <queue>

template <class W>
class HuffmanTreeNode {

public:
	HuffmanTreeNode<W>* _left;
	HuffmanTreeNode<W>* _right;
	HuffmanTreeNode<W>* _parent;
	W _weight;  //以此变量为基点,进行构造huffman树,如果后续此节点的类型为自定义类型
				//那需要用户自己定义那种类型的一些符号重载,因为在构造Huffman树中
				//可能要用到这种类型的比较之类的
	HuffmanTreeNode(const W& weight = W())
		:_weight(weight)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr) 
	{}
};


template <class W>
class HuffmanTree {
	typedef HuffmanTreeNode<W> node;

	//仿函数,用于比较两个node*类型的变量的大小
	struct Compare {
		bool operator() (const node* left, const node* right) const {
			return (left->_weight > right->_weight);
		}
	};

public:
	HuffmanTree()
		:_root(nullptr) 
	{}

	//构造Huffman树,用vector保存要构造的节点里面的_weight的值,然后进行构造
	//mark是标记值,表示vw里面的值为mark的元素不需要进行构造成为huffman树的叶子节点
	HuffmanTree(const std::vector<W>& vw, const W& mark = W()) {
		//构造huffman树的方法:
		//1.用所有有用权值构造二叉树森林,为了方便后续取值,最好用优先级队列来构造
		//2.取森林中权值最小的两个根节点,在他们上面增加节点,构造更大的二叉树
		//一直到森林里面只剩下一个节点为止
		//3.剩下的一个节点就是Huffman树的根节点
		std::priority_queue<node*, std::vector<node*>, Compare> pqw;
		for (auto e : vw) {
			if (e != mark) {
				pqw.push(new node(e));
			}
		}
		while (pqw.size() > 1) {
			node* left = pqw.top();
			pqw.pop();
			node* right = pqw.top();
			pqw.pop();
			//构建更大的二叉树
			node* parent = new node(left->_weight + right->_weight);
			parent->_left = left;
			left->_parent = parent;
			parent->_right = right;
			right->_parent = parent;
			pqw.push(parent);
		}
		if (pqw.size() != 0) {
			_root = pqw.top();
		}
	}

	node* getRoot() {
		return _root;
	}

	~HuffmanTree() {
		Destroy(_root);
	}
private:
	void Destroy(node*& root) {
		if (root != nullptr) {
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}
	}
private:
	node* _root;
};